package source;

import org.junit.Test;

import java.util.*;

public class HashTable {
    /**
     * 赎金信
     * <p>
     * ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
     * 如果可以，返回 true ；否则返回 false.
     * magazine 中的每个字符只能在 ransomNote 中使用一次。
     * ransomNote 和 magazine 由小写英文字母组成
     *
     * @return 判断 ransomNote 能不能由 magazine 里面的字符构成。
     */
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] chars = new int[26];
        for (char c : magazine.toCharArray()) {
            chars[c - 'a'] = ++chars[c - 'a'];
        }

        for (char c : ransomNote.toCharArray()) {
            if (chars[c - 'a'] <= 0)
                return false;
            chars[c - 'a'] = --chars[c - 'a'];
        }

        return true;
    }

    /**
     * 同构字符串
     * 给定两个字符串 s 和 t ，判断它们是否是同构的。
     * 如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
     * 每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
     */
    public boolean isIsomorphic(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();
        if (sLen != tLen)
            return false;
        HashMap<Character, Character> map = new HashMap<>();
        for (int i = 0; i < sLen; i++) {
            map.put(s.charAt(i), t.charAt(i));
        }
        Collection<Character> values = map.values();
        HashSet<Character> characters = new HashSet<>(values);
        if (characters.size() != map.size())
            return false;
        for (int i = 0; i < sLen; i++) {
            if (t.charAt(i) != map.get(s.charAt(i)))
                return false;
        }
        return true;
    }

    /**
     * 单词规律
     * 给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。
     * 这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。
     */
    public boolean wordPattern(String pattern, String s) {
        HashMap<Character, String> map = new HashMap<>();
        HashSet<String> set = new HashSet<>();
        String[] strs = s.split(" ");
        if (strs.length != pattern.length())
            return false;
        for (int i = 0; i < pattern.length(); i++) {
            set.add(strs[i]);
            if (map.containsKey(pattern.charAt(i))) {
                if (!map.get(pattern.charAt(i)).equals(strs[i])) {
                    return false;
                }
            } else {
                map.put(pattern.charAt(i), strs[i]);
            }
        }
        return set.size() == map.size();
    }

    /**
     * 有效的字母异位词
     * <p>
     * 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的 字母异位词。
     */
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length())
            return false;
        HashMap<Character, Integer> map = new HashMap<>();
        char ch;
        for (int i = 0; i < s.length(); i++) {
            ch = s.charAt(i);
            if (map.containsKey(ch)) {
                map.put(ch, map.get(ch) + 1);
            } else
                map.put(ch, 1);
        }
        for (int i = 0; i < s.length(); i++) {
            ch = t.charAt(i);
            if (!map.containsKey(ch) || map.get(ch) <= 0) {
                return false;
            } else {
                map.put(ch, map.get(ch) - 1);
            }
        }
        return true;
    }

    @Test
    public void test12() {
        System.out.println(isAnagram("aba", "baa"));
//        int[] arr = new int[26];
//        System.out.println(arr[0]);
//    new ArrayList<>().add()
        String s = "asdcb";
        char[] charArray = s.toCharArray();
        Arrays.sort(charArray);
        System.out.println(charArray);
        boolean add = new ArrayList<>().add(charArray);
        List<char[]> list = new ArrayList<>();
        list.add(charArray);
        System.out.println(list.get(0));
        System.out.println(list.contains(new char[]{'a', 'b', 'c', 'd', 's'}));
        char[] chars = {'a', 'b', 'c', 'd', 's'};
        System.out.println(new String(charArray));


    }

    /**
     * 字母异位词分组
     * <p>
     * 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
     * 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
     *
     * @param strs strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
     * @return [["bat"],["nat","tan"],["ate","eat","tea"]]
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> list = new ArrayList<>();
        HashMap<String, Integer> map = new HashMap<>();
        int index = 0; // 记录索引
        for (int i = 0; i < strs.length; i++) {
            char[] chars = strs[i].toCharArray();
            Arrays.sort(chars);
            String s = new String(chars);
            if (!map.containsKey(s)) {
                map.put(s, index);
                System.out.println(map);
                System.out.println(list);
                list.add(new ArrayList<>());
                list.get(index).add(strs[i]);
                index++;
            } else {
                list.get(map.get(s)).add(strs[i]);
            }

        }

        return list;
    }

    @Test
    public void testGroupAnagrams() {
        System.out.println(groupAnagrams(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"}));
    }

    /**
     * 两数之和
     * <p>
     * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
     * 你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
     * 你可以按任意顺序返回答案。
     *
     * @param nums   整数数组
     * @param target 目标值
     * @return 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
     */
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{map.get(target - nums[i]), i};
            } else {
                map.put(nums[i], i);
            }
        }

        return null;
    }

    /**
     * 快乐数
     * 「快乐数」 定义为：
     * 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
     * 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
     * 如果这个过程 结果为 1，那么这个数就是快乐数。
     * 如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
     *
     * @param n 数字
     * @return n 是不是快乐数
     */
    public boolean isHappy(int n) {
        HashSet<Integer> set = new HashSet<>();
        int sum;
        int value;
        while (!set.contains(n)) {
            set.add(n);
            sum = 0;
            while (n > 0) {
                int d = n % 10;
                sum += d * d;
                n /= 10;
            }
            if (sum == 1)
                return true;
            n = sum;
        }
        return false;
    }

    /**
     * 给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，
     * 满足 nums[i] == nums[j] 且 abs(i - j) <= k 。
     *
     * @param nums 整数数组
     * @param k    整数
     * @return 如果存在，返回 true ；否则，返回 false 。
     */
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i]) && i - map.get(nums[i]) <= k) {
                return true;
            }
            map.put(nums[i], i);
        }
        return false;
    }

    /**
     * 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
     *
     * @param nums 给定一个未排序的整数数组
     * @return 找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
     */
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums)
            set.add(num);
        int result = 0;
        int len = 0;
        for (int num : set) {
            if (!set.contains(num - 1)) {
                len = 1;
                while (set.contains(num + len)) {
                    len++;
                }
                result = Math.max(result, len);
            }
        }
        return result;
    }
}
